//数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，
//等等。 
//
// 请写一个函数，求任意第n位对应的数字。 
//
// 
//
// 示例 1： 
//
// 输入：n = 3
//输出：3
// 
//
// 示例 2： 
//
// 输入：n = 11
//输出：0 
//
// 
//
// 限制： 
//
// 
// 0 <= n < 2^31 
// 
//
// 注意：本题与主站 400 题相同：https://leetcode-cn.com/problems/nth-digit/ 
//
// Related Topics 数学 二分查找 👍 356 👎 0


package leetcode.editor.cn;
class 数字序列中某一位的数字{
    public static void main(String[] args) {
        Solution solution = new 数字序列中某一位的数字().new Solution();
        int n = 11;
        int sum = 1; 
        while (n != 0){
            sum += (n + "").length();
            n--;
        }
        System.out.println(sum);
        System.out.println(solution.findNthDigit(11));
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    public int findNthDigit1(int n) {
        if (n < 10 )return n ;
        int digit = 1;
        long start = 1;
        long count = 9;
        while (n > count) { // 1.
            n -= count;
            digit += 1;
            start *= 10;
            count = digit * start * 9;
        }
        long num = start + (n - 1) / digit; // 2.
        return Long.toString(num).charAt((n - 1) % digit) - '0'; // 3.
    }
    
    public int findNthDigit(int n) {
        if (n < 10 )return n ;
        int digit = 2;
        long cur = 9, dit = 10;
        while (cur < n){
            cur += 9 * dit * digit;
            dit *= 10;
            digit++;
        }
        cur -= n;
        int mol = (int) (cur % (digit - 1));
        int div = (int) (cur / (digit - 1));
        int res = (int) dit - 1 - div ;
        res = (int) (res  / Math.pow(10,mol) % 10);
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
